<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  <title>动态规划记忆化 | Hexo</title>
  <meta name="keywords" content="">
  <meta name="description" content="动态规划记忆化 | Hexo">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<meta name="description" content="第二章 线性表线性表：表内数据类型相同，有限序列 本章将以总结的形式展现： 2.1 顺序表与链式表的区别     顺序表 链式表     存取 随机存取 顺序存取   结构 顺序存储（连续） 随机存储（不连续）   空间分配 静态存储（可以动态分配） 动态存储   操作 查找 O(1) ,插入和删除O（n） 查找 O(n) ,插入和删除O（1）   缺点 插入删除不便，长度不可以改变 查找速度慢，">
<meta property="og:type" content="article">
<meta property="og:title" content="数据结构">
<meta property="og:url" content="http://yoursite.com/2021/03/12/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/index.html">
<meta property="og:site_name" content="Hexo">
<meta property="og:description" content="第二章 线性表线性表：表内数据类型相同，有限序列 本章将以总结的形式展现： 2.1 顺序表与链式表的区别     顺序表 链式表     存取 随机存取 顺序存取   结构 顺序存储（连续） 随机存储（不连续）   空间分配 静态存储（可以动态分配） 动态存储   操作 查找 O(1) ,插入和删除O（n） 查找 O(n) ,插入和删除O（1）   缺点 插入删除不便，长度不可以改变 查找速度慢，">
<meta property="og:locale" content="en_US">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/23/171951-630686.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/23/171844-136893.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/19/203103-111988.jpeg">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/23/171839-101678.jpeg">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/23/200119-510473.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202103/05/113954-515448.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/23/203146-263519.jpeg">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/19/153239-688589.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/19/153248-836462.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/19/153259-101399.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202103/11/113055-306258.jpeg">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/19/151817-474283.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/02/103950-168345.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/02/105245-140913.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/19/153313-134836.png">
<meta property="article:published_time" content="2021-03-11T16:00:00.000Z">
<meta property="article:modified_time" content="2021-03-11T07:19:09.038Z">
<meta property="article:author" content="MOLU">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/23/171951-630686.png">


<link rel="icon" href="/img/avatar.jpg">

<link href="/css/style.css?v=1.1.0" rel="stylesheet">

<link href="/css/hl_theme/github.css?v=1.1.0" rel="stylesheet">

<link href="//cdn.jsdelivr.net/npm/animate.css@4.1.0/animate.min.css" rel="stylesheet">

<script src="//cdn.jsdelivr.net/npm/jquery@3.5.1/dist/jquery.min.js"></script>
<script src="/js/titleTip.js?v=1.1.0" ></script>

<script src="//cdn.jsdelivr.net/npm/highlightjs@9.16.2/highlight.pack.min.js"></script>
<script>
    hljs.initHighlightingOnLoad();
</script>

<script src="//cdn.jsdelivr.net/npm/nprogress@0.2.0/nprogress.min.js"></script>



<script src="//cdn.jsdelivr.net/npm/jquery.cookie@1.4.1/jquery.cookie.min.js" ></script>

<script src="/js/iconfont.js?v=1.1.0" ></script>

<meta name="generator" content="Hexo 5.0.0"></head>
<div style="display: none">
  <input class="theme_disqus_on" value="false">
  <input class="theme_preload_comment" value="">
  <input class="theme_blog_path" value="">
  <input id="theme_shortcut" value="true" />
</div>


<body>
<aside class="nav">
    <div class="nav-left">
        <a href="/" class="avatar_target">
    <img class="avatar" src="/img/avatar.jpg" />
</a>
<div class="author">
    <span>MOLU</span>
</div>

<div class="icon">
    
        
        <a title="rss" href="/atom.xml" target="_blank">
            
                <i class="iconfont icon-rss"></i>
            
        </a>
        
    
        
        <a title="github" href="https://github.com/molu-ggg" target="_blank">
            
                <i class="iconfont icon-github"></i>
            
        </a>
        
    
        
    
        
    
        
        <a title="email" href="mailto:2572876783@qq.com" target="_blank">
            
                <i class="iconfont icon-email"></i>
            
        </a>
        
    
</div>




<ul>
    <li><div class="all active" data-rel="All">All<small>(35)</small></div></li>
    
        
            
            <li><div data-rel="AI论文">AI论文<small>(5)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="专业知识">专业知识<small>(2)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="数学">数学<small>(2)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="机器学习">机器学习<small>(12)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="经典算法">经典算法<small>(10)</small></div>
                
            </li>
            
        
    
</ul>
<div class="left-bottom">
    <div class="menus">
    
    
    
    
    </div>
    <div><a class="about  hasFriend  site_url"  href="/about">About</a><a style="width: 50%"  class="friends">Friends</a></div>
</div>
<input type="hidden" id="yelog_site_posts_number" value="35">

<div style="display: none">
    <span id="busuanzi_value_site_uv"></span>
    <span id="busuanzi_value_site_pv"></span>
</div>

    </div>
    <div class="nav-right">
        <div class="friends-area">
    <div class="friends-title">
        Links
        <i class="iconfont icon-left"></i>
    </div>
    <div class="friends-content">
        <ul>
            
            <li><a target="_blank" href="http://yelog.org/">叶落阁</a></li>
            
        </ul>
    </div>
</div>
        <div class="title-list">
    <div class="right-top">
        <div id="default-panel">
            <i class="iconfont icon-search" data-title="搜索 快捷键 i"></i>
            <div class="right-title">All</div>
            <i class="iconfont icon-file-tree" data-title="切换到大纲视图 快捷键 w"></i>
        </div>
        <div id="search-panel">
            <i class="iconfont icon-left" data-title="返回"></i>
            <input id="local-search-input" />
            <label class="border-line" for="input"></label>
            <i class="iconfont icon-case-sensitive" data-title="大小写敏感"></i>
            <i class="iconfont icon-tag" data-title="标签"></i>
        </div>
        <div id="outline-panel" style="display: none">
            <div class="right-title">大纲</div>
            <i class="iconfont icon-list" data-title="切换到文章列表"></i>
        </div>
    </div>

    <div class="tags-list">
    <input id="tag-search" />
    <div class="tag-wrapper">
        
            <li class="article-tag-list-item">
                <i class="iconfont icon-tag"></i><a>50</a>
            </li>
        
            <li class="article-tag-list-item">
                <i class="iconfont icon-tag"></i><a>AI</a>
            </li>
        
            <li class="article-tag-list-item">
                <i class="iconfont icon-tag"></i><a>数据结构，最短路径，图</a>
            </li>
        
            <li class="article-tag-list-item">
                <i class="iconfont icon-tag"></i><a>机器学习</a>
            </li>
        
            <li class="article-tag-list-item">
                <i class="iconfont icon-tag"></i><a>相似度计算</a>
            </li>
        
    </div>

</div>

    
    <div id="local-search-result">

    </div>
    
    <nav id="title-list-nav">
        
        <a id="top" class="All 经典算法 "
           href="/2020/07/20/b_leetcode/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="leetcode &amp; 蓝桥">leetcode &amp; 蓝桥</span>
            <span class="post-date" title="2020-07-20 00:00:00">2020/07/20</span>
        </a>
        
        <a id="top" class="All AI论文 "
           href="/2020/07/10/d_GAT/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="GAT">GAT</span>
            <span class="post-date" title="2020-07-10 08:50:20">2020/07/10</span>
        </a>
        
        <a  class="All 专业知识 "
           href="/2021/03/12/%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="计算机组成原理">计算机组成原理</span>
            <span class="post-date" title="2021-03-12 00:00:00">2021/03/12</span>
        </a>
        
        <a  class="All 专业知识 "
           href="/2021/03/12/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="数据结构">数据结构</span>
            <span class="post-date" title="2021-03-12 00:00:00">2021/03/12</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2020/12/05/b_%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E4%B8%8E%E8%AE%B0%E5%BF%86%E5%8C%96%E6%90%9C%E7%B4%A2/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="动态规划记忆化">动态规划记忆化</span>
            <span class="post-date" title="2020-12-05 00:00:00">2020/12/05</span>
        </a>
        
        <a  class="All AI论文 "
           href="/2020/07/25/d_300-paperDAT/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="DAT for recommender">DAT for recommender</span>
            <span class="post-date" title="2020-07-25 08:50:20">2020/07/25</span>
        </a>
        
        <a  class="All 数学 "
           href="/2020/07/20/a_%E7%AE%97%E6%B3%95/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="算法总结">算法总结</span>
            <span class="post-date" title="2020-07-20 00:00:00">2020/07/20</span>
        </a>
        
        <a  class="All 数学 "
           href="/2020/07/20/a_%E6%95%B0%E5%AD%A6/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="数学">数学</span>
            <span class="post-date" title="2020-07-20 00:00:00">2020/07/20</span>
        </a>
        
        <a  class="All "
           href="/2020/07/05/%E5%AF%B9%E9%9A%90%E7%A7%98%E7%9A%84%E8%A7%92%E8%90%BD%E7%94%B5%E8%A7%86%E5%89%A7%E7%9A%84%E6%84%9F%E6%82%9F%E4%BB%A5%E5%8F%8A%E8%AE%A4%E8%AF%86/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="对隐秘的角落电视剧的感悟以及认识">对隐秘的角落电视剧的感悟以及认识</span>
            <span class="post-date" title="2020-07-05 00:00:00">2020/07/05</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2020/07/04/a_%E6%A8%A1%E6%9D%BF%E5%BA%93/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="模板库">模板库</span>
            <span class="post-date" title="2020-07-04 08:50:20">2020/07/04</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2020/07/04/a_%E7%99%BE%E5%BA%A6%E6%8A%80%E6%9C%AF%E8%AE%A4%E8%AF%81/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="百度技术认证">百度技术认证</span>
            <span class="post-date" title="2020-07-04 08:50:20">2020/07/04</span>
        </a>
        
        <a  class="All AI论文 "
           href="/2020/07/01/d_GCN%E8%AE%BA%E6%96%87%E8%A7%A3%E8%AF%BB/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="GCN">GCN</span>
            <span class="post-date" title="2020-07-01 08:50:20">2020/07/01</span>
        </a>
        
        <a  class="All AI论文 "
           href="/2020/06/04/d_word2vec_node2vec/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="Word2vec &amp; Node2vec">Word2vec &amp; Node2vec</span>
            <span class="post-date" title="2020-06-04 08:50:20">2020/06/04</span>
        </a>
        
        <a  class="All AI论文 "
           href="/2020/05/05/d_GAN/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="GAN">GAN</span>
            <span class="post-date" title="2020-05-05 08:50:20">2020/05/05</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2020/05/04/d_Deepwalk/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="DEEPWALK">DEEPWALK</span>
            <span class="post-date" title="2020-05-04 08:50:20">2020/05/04</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2020/02/15/b_%E8%B4%AA%E5%BF%83/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="贪心与动态规划">贪心与动态规划</span>
            <span class="post-date" title="2020-02-15 00:00:00">2020/02/15</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2020/02/12/a_2020/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="机器学习零散知识记录">机器学习零散知识记录</span>
            <span class="post-date" title="2020-02-12 00:00:00">2020/02/12</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2020/02/12/b_%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="动态规划——背包问题">动态规划——背包问题</span>
            <span class="post-date" title="2020-02-12 00:00:00">2020/02/12</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2020/02/03/b_%E8%93%9D%E6%A1%A5%E6%9D%AF%E7%BB%83%E4%B9%A0%E9%A2%98/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="蓝桥杯">蓝桥杯</span>
            <span class="post-date" title="2020-02-03 00:00:00">2020/02/03</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2020/01/20/c_%E5%86%B3%E7%AD%96%E6%A0%91/"
           data-tag="50"
           data-author="" >
            <span class="post-title" title="决策树总结">决策树总结</span>
            <span class="post-date" title="2020-01-20 00:00:00">2020/01/20</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2020/01/12/b_%E5%85%A8%E6%8E%92%E5%88%97/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="全排列">全排列</span>
            <span class="post-date" title="2020-01-12 00:00:00">2020/01/12</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2019/12/02/b_%E6%9C%89%E7%A9%B7%E8%87%AA%E5%8A%A8%E6%9C%BA/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="有穷自动机">有穷自动机</span>
            <span class="post-date" title="2019-12-02 00:00:00">2019/12/02</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2019/11/20/b_%E9%94%99%E6%8E%92%E5%85%AC%E5%BC%8F/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="错排公式">错排公式</span>
            <span class="post-date" title="2019-11-20 00:00:00">2019/11/20</span>
        </a>
        
        <a  class="All "
           href="/2019/10/29/a_%E5%BC%97%E6%B4%9B%E4%BC%8A%E5%BE%B7/"
           data-tag="数据结构，最短路径，图"
           data-author="" >
            <span class="post-title" title="最短路径之弗洛伊德算法">最短路径之弗洛伊德算法</span>
            <span class="post-date" title="2019-10-29 00:00:00">2019/10/29</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2019/08/04/c_BPR/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="贝叶斯">贝叶斯</span>
            <span class="post-date" title="2019-08-04 08:50:20">2019/08/04</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2019/08/02/c_matrix/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="矩阵分解与正则化">矩阵分解与正则化</span>
            <span class="post-date" title="2019-08-02 08:25:59">2019/08/02</span>
        </a>
        
        <a  class="All "
           href="/2019/07/28/c_coordination1/"
           data-tag="AI,机器学习,相似度计算"
           data-author="" >
            <span class="post-title" title="协同过滤-上">协同过滤-上</span>
            <span class="post-date" title="2019-07-28 08:25:59">2019/07/28</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2019/07/26/c_cnn/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="cnn">cnn</span>
            <span class="post-date" title="2019-07-26 18:54:51">2019/07/26</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2019/07/22/c_coordination2/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="协同过滤—下">协同过滤—下</span>
            <span class="post-date" title="2019-07-22 18:54:26">2019/07/22</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2019/07/22/c_kmeans/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="K-means算法">K-means算法</span>
            <span class="post-date" title="2019-07-22 18:53:07">2019/07/22</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2019/07/21/c_nerve2/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="神经网络-下">神经网络-下</span>
            <span class="post-date" title="2019-07-21 11:37:18">2019/07/21</span>
        </a>
        
        <a  class="All "
           href="/2019/07/20/c_nerve1/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="神经网络—上">神经网络—上</span>
            <span class="post-date" title="2019-07-20 17:29:10">2019/07/20</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2019/06/22/c_gradient/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="线性回归与梯度下降算法">线性回归与梯度下降算法</span>
            <span class="post-date" title="2019-06-22 08:26:36">2019/06/22</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2019/06/19/c_flyback/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="线性回归">线性回归</span>
            <span class="post-date" title="2019-06-19 00:00:00">2019/06/19</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2019/05/20/b_%E8%A7%86%E9%A2%91%E7%BB%8F%E5%85%B8%E7%AE%97%E6%B3%95/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="简单入门算法">简单入门算法</span>
            <span class="post-date" title="2019-05-20 00:00:00">2019/05/20</span>
        </a>
        
        <div id="no-item-tips">

        </div>
    </nav>
    <div id="outline-list">
    </div>
</div>
    </div>
    <div class="hide-list">
        <div class="semicircle" data-title="切换全屏 快捷键 s">
            <div class="brackets first"><</div>
            <div class="brackets">&gt;</div>
        </div>
    </div>
</aside>
<div id="post">
    <div class="pjax">
        <article id="post-b_动态规划与记忆化搜索" class="article article-type-post" itemscope itemprop="blogPost">
    
        <h1 class="article-title">动态规划记忆化</h1>
    
    <div class="article-meta">
        
        
        
        <span class="book">
            <i class="iconfont icon-category"></i>
            
            
            <a  data-rel="经典算法">经典算法</a>
            
        </span>
        
        
    </div>
    <div class="article-meta">
        
            Created At : <time class="date" title='Updated At: 2020-08-09 14:28:07'>2020-12-05 00:00</time>
        
    </div>
    <div class="article-meta">
        
        
        <span id="busuanzi_container_page_pv">
            Views 👀 :<span id="busuanzi_value_page_pv">
                <span class="count-comment">
                    <span class="spinner">
                      <div class="cube1"></div>
                      <div class="cube2"></div>
                    </span>
                </span>
            </span>
        </span>
        
        
    </div>
    
    <div class="toc-ref">
    
        <ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92"><span class="toc-text">动态规划</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E7%89%B9%E5%BE%81%EF%BC%9A"><span class="toc-text">特征：</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BB%B7%E5%80%BC%E4%B8%80%E5%AE%9A%EF%BC%8C%E7%94%A8%E6%9C%80%E5%B0%91%E7%9A%84%E4%B8%AA%E6%95%B0"><span class="toc-text">价值一定，用最少的个数</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%B8%AA%E6%95%B0%EF%BC%88%E4%BD%93%E7%A7%AF%E7%AD%89%EF%BC%89%E4%B8%80%E5%AE%9A%EF%BC%8C%E8%A3%85%E6%9C%80%E5%A4%A7%E7%9A%84%E4%BB%B7%E5%80%BC"><span class="toc-text">个数（体积等）一定，装最大的价值</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E7%BB%8F%E5%85%B8%E7%9A%84%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%EF%BC%9A%E4%B8%80%E5%AE%9A%E5%BE%97%E5%AE%B9%E9%87%8F%EF%BC%8C%E8%A3%85%E8%B6%B3%E5%A4%9F%E5%A4%9A%E7%9A%84%E7%9A%84%E4%BB%B7%E5%80%BC"><span class="toc-text">经典的背包问题：一定得容量，装足够多的的价值</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%B8%80%E5%AE%9A%EF%BC%8C%E6%B1%82%E7%A7%8D%E7%B1%BB%E4%B8%AA%E6%95%B0"><span class="toc-text">一定，求种类个数</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%B0%8FA%E7%82%B9%E8%8F%9C%EF%BC%9A%E6%B1%82%E7%A7%8D%E7%B1%BB%E4%B8%AA%E6%95%B0"><span class="toc-text">小A点菜：求种类个数</span></a></li></ol></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E4%BB%A5%E4%B8%8B%E6%98%AF%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%9A%84%E5%85%B6%E4%BB%96%E5%BA%94%E7%94%A8%EF%BC%9A"><span class="toc-text">以下是动态规划的其他应用：</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%9C%80%E9%95%BF%E9%80%92%E5%A2%9E%E5%BA%8F%E5%88%97%EF%BC%9A"><span class="toc-text">最长递增序列：</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#Tony%E7%9A%84%E4%BB%BB%E5%8A%A1"><span class="toc-text">Tony的任务</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E4%B9%8B%E8%AE%B0%E5%BF%86%E5%8C%96%E6%90%9C%E7%B4%A2"><span class="toc-text">动态规划之记忆化搜索</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%BB%91%E9%9B%AA%E9%97%AE%E9%A2%98"><span class="toc-text">滑雪问题</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E9%AB%98%E7%AD%89%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92"><span class="toc-text">高等动态规划</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%8C%BA%E9%97%B4DP"><span class="toc-text">区间DP</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E7%9F%B3%E5%AD%90%E5%BD%92%E5%B9%B6"><span class="toc-text">石子归并</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%B2%A1%E6%9C%89%E4%B8%8A%E5%8F%B8%E7%9A%84%E8%88%9E%E4%BC%9A"><span class="toc-text">没有上司的舞会</span></a></li></ol></li></ol></li></ol>
    
<style>
    .left-col .switch-btn,
    .left-col .switch-area {
        display: none;
    }
    .toc-level-4 i,
    .toc-level-4 ol {
        display: none !important;
    }
</style>
</div>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h1 id="动态规划"><a href="#动态规划" class="headerlink" title="动态规划"></a>动态规划</h1><h2 id="特征："><a href="#特征：" class="headerlink" title="特征："></a>特征：</h2><p>当前最优解的前束所有的最优解都已经解决</p>
<ol>
<li>最优子结构：就是说，问题的子问题也是最优的（贪心也具有）</li>
<li>子结构可以多次在后面的状态应用：F(3)，F(6)=F(3)+w(3),F(9)=F(3)+w(6),F是当前的最优解，这个是明显特征。</li>
<li>前面的状态可以改变</li>
</ol>
<p>​     </p>
<h2 id="价值一定，用最少的个数"><a href="#价值一定，用最少的个数" class="headerlink" title="价值一定，用最少的个数"></a>价值一定，用最少的个数</h2><p>当前子问题的解将由之前已经解决的子问题某一个或几个的解推出，不一定是前一个子问题的解，两个相邻问的解肯那个没有关系。</p>
<p>首先我们思考一个问题，现在有1,3,5三种硬币，如何用最少的硬币凑够i元(i&lt;11)？为什么要这么问呢？两个原因：</p>
<p>1.当我们遇到一个大问题时，总是习惯把问题的 规模变小，这样便于分析讨论。 </p>
<p>2.这个规模变小后的问题和原来的问题是同质的，除了规模变小，其它的都是一样的，本质上它还是同一个问题(规模变小后的问题其实是原问题的子问题)。</p>
<p>动态规划是一步步规模变大的问题。</p>
<p>现在我要拼7元钱</p>
<p>解决方案是：</p>
<ul>
<li><p>当i=0,d(i)=0;</p>
</li>
<li><p>i=2之前只有一种硬币：</p>
</li>
<li><p>i=1时，d(1)=d(1-1)+1</p>
</li>
<li><p>i=2 ，d(2)=d(2-1)+1;</p>
</li>
<li><p>i=3-5有两种硬币可以选择:</p>
</li>
<li><p>i=3时,①d(3-1)+1;</p>
</li>
<li><p>②d(3-3)+1;</p>
</li>
<li><p>d（3）=min(①，②)</p>
</li>
<li><p>i=4,d(4)=min(d(4-1)+1,d(4-3)+1);</p>
</li>
<li><p>i=5,d(5)=min(d(5-1)+1,d(5-3)+1,d(5-5)+1);</p>
</li>
<li><p>i=6,d(6)=min(d(6-1)+1,d(6-3)+1,d(6-5)+1);</p>
</li>
<li><p>i=7,d(7)=min(d(7-1)+1,d(7-3)+1,d(7-5)+1)//就三种硬币可以选择就是</p>
</li>
</ul>
<p>实际上是一种递归问题。</p>
<p>1.动态规划转移方程的寻找：</p>
<p><a target="_blank" rel="noopener" href="https://www.cnblogs.com/fu11211129/p/4276213.html">https://www.cnblogs.com/fu11211129/p/4276213.html</a></p>
<p>一般来说，DP都是可以转化成二维的，当然也有多维DP：</p>
<p>行列分别是两个元素：列如，上述可以行——钱，列——硬币种类，F(x,y)内容就是当前，y元前x中硬币最少的硬币数：（以下图更跟这问题无关）</p>
<p><img src="https://moluggg.oss-cn-qingdao.aliyuncs.com/img/aa3f9ae4cdac06b69618b57bc09326ce_2755780-1G130103202634.jpg" alt=""></p>
<p><img src="https://moluggg.oss-cn-qingdao.aliyuncs.com/img/aa3f9ae4cdac06b69618b57bc09326ce_2755780-1G130103202634.jpg" alt=""></p>
<p>代码如下：</p>
<pre><code class="lang-c++">for  (i=1;i&lt;=n;i++)&amp;#123;//钱 
    for (j=1;j&lt;=m;j++)&amp;#123;//硬币种类 
        F[i][j]=min(F[i-1][j],F[i-1][j-a[i]]+1); //a[i]表示第i中代表 多少钱
        //就是不用改硬币的最佳方案，和跟用该硬币的最佳方案两种方案中选最佳方案 
    &amp;#125;
&amp;#125;
</code></pre>
<p>一般而言，我们一般采用的是一维数组表示：</p>
<p>因为我们不必重视钱从1到n的变化过程，只需要随着硬币种类的增加，改变同等钱的情况下的所需要的硬币数就行。转移方程也已改写成以下：</p>
<pre><code class="lang-c++">for(i=1;i&lt;=m;i++)&amp;#123;  //硬币种类  
    for (j=1；j&lt;=n;j++)&amp;#123;  
        //这里大家要注意 ，这个是完全背包问题：每件物品有无限个
        F[j]=min(F[j],F[j-a[i]]+1) ;
    &amp;#125;
</code></pre>
<h2 id="个数（体积等）一定，装最大的价值"><a href="#个数（体积等）一定，装最大的价值" class="headerlink" title="个数（体积等）一定，装最大的价值"></a>个数（体积等）一定，装最大的价值</h2><h3 id="经典的背包问题：一定得容量，装足够多的的价值"><a href="#经典的背包问题：一定得容量，装足够多的的价值" class="headerlink" title="经典的背包问题：一定得容量，装足够多的的价值"></a>经典的背包问题：一定得容量，装足够多的的价值</h3><p>后续其他背包问题背包问题：</p>
<p>实际上就是：</p>
<p>容量m,最佳价值w</p>
<p><img src="https://moluggg.oss-cn-qingdao.aliyuncs.com/img/20200202122624.png" alt=""></p>
<p>多个：</p>
<p>m=1,w(1)</p>
<p>m=2,w(2)=max(w(1)+weight(1),weight(2))</p>
<p>m=3,w(3)=max(weight(3),w(2)+weight(1),w(1)+weight(2))</p>
<p>m=4,w(4)=max(weight(4),w(3)+weight(1),w(2)+weight(2),w(1)+weight(3))</p>
<p>每件物品只有一个：</p>
<p>表格法：</p>
<p><img src="https://moluggg.oss-cn-qingdao.aliyuncs.com/img/20200117212928.png" alt=""></p>
<p>某一件物品放与不放的影响  </p>
<p>F(i,j)表示在体积为j的别背包中放前i件物品的最优解：</p>
<p>每一次，都在放该第i件物品与不放中挣扎比较</p>
<p>①如果放：要预留出i物品的体积m(i)，然后加上i的价值weight。F(i-1,j-m(i))+weight(i);</p>
<p>②如果不放：价值跟前i-1一样  ：F(i-1,j)</p>
<p>F(i,j)取两种情况的最大值：</p>
<script type="math/tex; mode=display">
F(i,j)=max(F(i-1,j-m(i))+weight(i),F(i-1,j))</script><p>问：贪心能解决这个问题？不能 ，因为空间的限制，虽然我们每次可以取价值量/体积最大的东西，但是由于空间上的束缚，你不知道，这个东西是否能存的上，且存入之后，另外的多余空间是否能存上其他物品，不能就造成浪费，与贪心的本质矛盾。</p>
<p>可以改写成一维数组：</p>
<pre><code class="lang-c++">for(i=1;i&lt;=m;i++)&amp;#123;  //硬币种类  
    for (j=n;j&gt;=m[i];j--)&amp;#123;  
        F[j]=min(F[j],F[j-m[i]]+weight(i)) ;
    &amp;#125;
</code></pre>
<p>到这里，会看出跟硬币问题的别，是j—为什么要倒着那：</p>
<p>首先我们要看出跟哪道题的区别：这道题是有限个物体，每件物品只能拿一次。</p>
<p>我们假设正序，且有以下可能：</p>
<p>i=3时，F(3)的最优解，F(6)=F(3)+w(3)是F（6）的最优解，F（9）=F（6）+w(3)是F(9)的最优解，也就是说F（9）的最优解里，有多个3组成的，但实际3只有一个</p>
<p>现在倒序：</p>
<p>i=3,j=9时，F（9)的最优解还是F（6）+w(3)的话，F（6)一定不包含3的存在，因为此时的F(6)还没有更新i=3的情况，还是i=2的最优解，同理F(6)最多有一个2。且当j=6时才决定是否要3</p>
<h2 id="一定，求种类个数"><a href="#一定，求种类个数" class="headerlink" title="一定，求种类个数"></a>一定，求种类个数</h2><h3 id="小A点菜：求种类个数"><a href="#小A点菜：求种类个数" class="headerlink" title="小A点菜：求种类个数"></a><a target="_blank" rel="noopener" href="https://www.luogu.com.cn/problem/P1164">小A点菜</a>：求种类个数</h3><p>思路：在吃与不吃中抉择：</p>
<p>F(i,j)是前i件物品，花刚好j元的种类个数</p>
<p>若吃：F(i-1,j-w(i)) *1</p>
<p>若不吃：F(i-1,j)</p>
<p>当然，还要吃得起才可以吃</p>
<pre><code>if (j&gt;w(i)) 

F(i,j)=F(i-1,j-w(i))+F(i-1,j)

else F(i,j)=F(i-1,j)
</code></pre><p>初始化F(i,0)=1  因为所有钱买一道菜也是一种方案。</p>
<h1 id="以下是动态规划的其他应用："><a href="#以下是动态规划的其他应用：" class="headerlink" title="以下是动态规划的其他应用："></a>以下是动态规划的其他应用：</h1><h2 id="最长递增序列："><a href="#最长递增序列：" class="headerlink" title="最长递增序列："></a><a target="_blank" rel="noopener" href="https://www.luogu.com.cn/problem/P1020">最长递增序列：</a></h2><p>点击可以查看此类型</p>
<p>2 19 18 3 5 7</p>
<p>类似这样的，本质上求一段连续的字符串找可以间断找最长的上升、下降，不降，不升的序列。</p>
<h2 id="Tony的任务"><a href="#Tony的任务" class="headerlink" title="Tony的任务"></a><a target="_blank" rel="noopener" href="https://www.luogu.com.cn/problem/P1280">Tony的任务</a></h2><p>这道题比较难理解</p>
<p>初步掌握动态规划问题，可以看看背包问题</p>
<p>多维动态</p>
<p>参考文章：</p>
<p><a target="_blank" rel="noopener" href="http://www.elecfans.com/dianzichangshi/20171130589302.html">动态规划</a></p>
<p><a target="_blank" rel="noopener" href="https://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741374.html">五大算法</a></p>
<h1 id="动态规划之记忆化搜索"><a href="#动态规划之记忆化搜索" class="headerlink" title="动态规划之记忆化搜索"></a>动态规划之记忆化搜索</h1><h2 id="滑雪问题"><a href="#滑雪问题" class="headerlink" title="滑雪问题"></a>滑雪问题</h2><pre><code class="lang-c++">#include&lt;iostream&gt;
#include&lt;cstdio&gt;
#include&lt;cstring&gt;
#include&lt;algorithm&gt;
using namespace std;
const int max_size=110;
int R,C;
int dir[4][2]=&amp;#123;&amp;#123;-1,0&amp;#125;,&amp;#123;0,1&amp;#125;,&amp;#123;1,0&amp;#125;,&amp;#123;0,-1&amp;#125;&amp;#125;;//四个方向
int h[max_size][max_size],dp[max_size][max_size];
int inMap(int x,int y)&amp;#123;//判断是否在地图内
    if(x&gt;=0&amp;&amp;x&lt;=R-1&amp;&amp;y&gt;=0&amp;&amp;y&lt;=C-1) return 1;
    return 0;
&amp;#125;
int max2(int a,int b,int c,int d)&amp;#123;//寻找最大值
    return max(max(a,b),max(c,d));
&amp;#125;
int dfs(int i,int j)&amp;#123;
    int nx,ny,down=0,up=0,left=0,right=0;
    if(dp[i][j]) return dp[i][j];
    nx=i+dir[0][0]; ny=j+dir[0][1];//第一个方向
    if(inMap(nx,ny))&amp;#123;
        if(h[i][j]&gt;h[nx][ny]) up=dfs(nx,ny);
    &amp;#125;
    nx=i+dir[1][0]; ny=j+dir[1][1];//第2个方向
    if(inMap(nx,ny))&amp;#123;
        if(h[i][j]&gt;h[nx][ny]) right=dfs(nx,ny);
    &amp;#125;
    nx=i+dir[2][0]; ny=j+dir[2][1];//第3个方向
    if(inMap(nx,ny))&amp;#123;
        if(h[i][j]&gt;h[nx][ny]) down=dfs(nx,ny);
    &amp;#125;
    nx=i+dir[3][0]; ny=j+dir[3][1];//第4个方向
    if(inMap(nx,ny))&amp;#123;
        if(h[i][j]&gt;h[nx][ny]) left=dfs(nx,ny);
    &amp;#125;
    dp[i][j]=max2(up,down,left,right)+1;//判找四个方向哪个最长！是最长！
    return dp[i][j];
&amp;#125;
int main()&amp;#123;
    scanf(&quot;%d%d&quot;,&amp;R,&amp;C);
    memset(h,0,sizeof(h));
    memset(dp,0,sizeof(dp));
    for(int i=0;i&lt;R;i++)&amp;#123;
        for(int j=0;j&lt;C;j++)&amp;#123;
            scanf(&quot;%d&quot;,&amp;h[i][j]);
        &amp;#125;
    &amp;#125;
    int ans=-1;
    for(int i=0;i&lt;R;i++)&amp;#123;
        for(int j=0;j&lt;C;j++)&amp;#123;
            ans=max(ans,dfs(i,j));
        &amp;#125;
    &amp;#125;
    printf(&quot;%d\n&quot;,ans);
&amp;#125;
</code></pre>
<h1 id="高等动态规划"><a href="#高等动态规划" class="headerlink" title="高等动态规划"></a>高等动态规划</h1><p>这里说高级，其实也不是很难的意思。前面我们学的都是线性动态规划等一般可以用二维数组可以解决的。</p>
<p>现在，我们见一见其他的不可以或者难以用动态规划解决的。</p>
<p>有以下几种：</p>
<p>状态DP，区间DP，多维DP</p>
<h2 id="区间DP"><a href="#区间DP" class="headerlink" title="区间DP"></a>区间DP</h2><h3 id="石子归并"><a href="#石子归并" class="headerlink" title="石子归并"></a><a target="_blank" rel="noopener" href="https://www.cnblogs.com/IThaitian/archive/2012/07/12/2588704.html">石子归并</a></h3><p>受到空间上的束缚，贪心思想每次拿到两个最优解失效，必须找到一个结点分成两个区域，两个区域满足相加最优解最大，使完成贪心的使命。</p>
<h3 id="没有上司的舞会"><a href="#没有上司的舞会" class="headerlink" title="没有上司的舞会"></a><a target="_blank" rel="noopener" href="https://www.luogu.com.cn/problem/P1352">没有上司的舞会</a></h3><p>典型的树状结构</p>

      
       <hr><span style="font-style: italic;color: gray;"> 转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 2572876783@qq.com </span>
    </div>
</article>


<p>
    <a  class="dashang" onclick="dashangToggle()">💰</a>
</p>






    
        <!-- MathJax配置，可通过单美元符号书写行内公式等 -->
<script type="text/x-mathjax-config">
    MathJax.Hub.Config({
    "HTML-CSS": {
        preferredFont: "TeX",
        availableFonts: ["STIX","TeX"],
        linebreaks: { automatic:true },
        EqnChunk: (MathJax.Hub.Browser.isMobile ? 10 : 50)
    },
    tex2jax: {
        inlineMath: [ ["$", "$"], ["\\(","\\)"] ],
        processEscapes: true,
        ignoreClass: "tex2jax_ignore|dno",
        skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
    },
    TeX: {
        equationNumbers: { autoNumber: "AMS" },
        noUndefined: { attributes: { mathcolor: "red", mathbackground: "#FFEEEE", mathsize: "90%" } },
        Macros: { href: "{}" }
    },
    messageStyle: "none"
    });
</script>
<!-- 给MathJax元素添加has-jax class -->
<script type="text/x-mathjax-config">
    MathJax.Hub.Queue(function() {
        var all = MathJax.Hub.getAllJax(), i;
        for(i=0; i < all.length; i += 1) {
            all[i].SourceElement().parentNode.className += ' has-jax';
        }
    });
</script>
<!-- 通过连接CDN加载MathJax的js代码 -->
<script type="text/javascript" async
        src="//cdn.jsdelivr.net/npm/mathjax@2.7.8/unpacked/MathJax.js?config=TeX-MML-AM_CHTML">
</script>
<input type="hidden" id="MathJax-js"
        value="//cdn.jsdelivr.net/npm/mathjax@2.7.8/unpacked/MathJax.js?config=TeX-MML-AM_CHTML">
</input>
    




    </div>
    <div class="copyright">
        <p class="footer-entry">
    ©2016-2020 MOLU
</p>
<p class="footer-entry">Built with <a href="https://hexo.io/" target="_blank">Hexo</a> and <a href="https://github.com/yelog/hexo-theme-3-hexo" target="_blank">3-hexo</a> theme</p>

    </div>
    <div class="full-toc">
        <button class="full" data-title="切换全屏 快捷键 s"><span class="min "></span></button>
<a class="" id="rocket" ></a>

    </div>
</div>

<div class="hide_box" onclick="dashangToggle()"></div>
<div class="shang_box">
    <a class="shang_close"  onclick="dashangToggle()">×</a>
    <div class="shang_tit">
        <p>Help us with donation</p>
    </div>
    <div class="shang_payimg">
        <div class="pay_img">
            <img src="/img/alipay.jpg" class="alipay" title="扫码支持">
            <img src="/img/weixin.jpg" class="weixin" title="扫码支持">
        </div>
    </div>
    <div class="shang_payselect">
        <span><label><input type="radio" name="pay" checked value="alipay">alipay</label></span><span><label><input type="radio" name="pay" value="weixin">weixin</label></span>
    </div>
</div>


</body>
<script src="/js/jquery.pjax.js?v=1.1.0" ></script>

<script src="/js/script.js?v=1.1.0" ></script>
<script>
    var img_resize = 'default';
    function initArticle() {
        /*渲染对应的表格样式*/
        
            $("#post .pjax table").addClass("green_title");
        

        /*渲染打赏样式*/
        
        $("input[name=pay]").on("click", function () {
            if($("input[name=pay]:checked").val()=="weixin"){
                $(".shang_box .shang_payimg .pay_img").addClass("weixin_img");
            } else {
                $(".shang_box .shang_payimg .pay_img").removeClass("weixin_img");
            }
        })
        

        /*高亮代码块行号*/
        

        /*访问数量*/
        
        $.getScript("//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js");
        

        /*代码高亮，行号对齐*/
        $('.pre-numbering').css('line-height',$('.has-numbering').css('line-height'));

        
        
    }

    /*打赏页面隐藏与展示*/
    
    function dashangToggle() {
        $(".shang_box").fadeToggle();
        $(".hide_box").fadeToggle();
    }
    

</script>

<!--加入行号的高亮代码块样式-->

<!--自定义样式设置-->
<style>
    
    
    .nav {
        width: 542px;
    }
    .nav.fullscreen {
        margin-left: -542px;
    }
    .nav-left {
        width: 120px;
    }
    
    
    @media screen and (max-width: 1468px) {
        .nav {
            width: 492px;
        }
        .nav.fullscreen {
            margin-left: -492px;
        }
        .nav-left {
            width: 100px;
        }
    }
    
    
    @media screen and (max-width: 1024px) {
        .nav {
            width: 492px;
            margin-left: -492px
        }
        .nav.fullscreen {
            margin-left: 0;
        }
    }
    
    @media screen and (max-width: 426px) {
        .nav {
            width: 100%;
        }
        .nav-left {
            width: 100%;
        }
    }
    
    
    .nav-right .title-list nav a .post-title, .nav-right .title-list #local-search-result a .post-title {
        color: #383636;
    }
    
    
    .nav-right .title-list nav a .post-date, .nav-right .title-list #local-search-result a .post-date {
        color: #5e5e5f;
    }
    
    
    .nav-right nav a.hover, #local-search-result a.hover{
        background-color: #e2e0e0;
    }
    
    

    /*列表样式*/
    

    /* 背景图样式 */
    
    


    /*引用块样式*/
    

    /*文章列表背景图*/
    

    
</style>







</html>
